10762. Ряд солдат

Имеется ряд n солдат, пронумерованных 0 до n – 1. Все они расположены таким образом, что солдат с номером i может видеть только солдат с номерами от 0 до i – 1. Будем говорить, что солдат имеет четкую видимость, если его рост не меньше роста всех солдат, стоящих перед ним. Если он не имеет четкой видимости, это означает, что по крайней мере один из других солдат, стоящих перед ним, выше его.

Для каждого солдата определите, имеет ли он четкую видимость. Если нет, то найдите номер ближайшего предыдущего солдата, который выше его.

Вход. Первая строка содержит количество солдат n (1 ≤ n ≤ 10⁵). Вторая строка содержит n чисел – рост солдат.

Выход. Выведите n чисел. i - ое число должно содержать номер ближайшего предыдущего солдата, который выше i - го солдата по росту. Если i - ый солдат имеет четкую видимость, выведите -1.

Пример входа	Пример выхода
10 5 3 3 4 9 2 7 5 2 4	-1 0 0 0 -1 4 4 6 7 7

РЕШЕНИЕ

стек

Анализ алгоритма

Объявим стек пар, который будет хранить информацию о солдатах: их рост и индекс. Будем обрабатывать солдат по очереди, начиная с самого левого. При обработке i-го солдата:

· удалим из стека солдат, чей рост не превышает роста i-го солдата (то есть тех солдат, чей рост меньше или равен росту i-го солдата);

· солдат на вершине стека будет ближайшим предыдущим солдатом, рост которого превышает рост i – го солдата. Если стек оказывается пустым, то i-ый солдат имеет четкую видимость;

· занесем в стек информацию о текущем солдате, то есть пару (рост солдата, номер солдата);

В любой момент времени стек хранит солдат, отсортированных по убыванию их роста. Когда приходит новый солдат, из стека удаляются все солдаты с меньшим или равным его ростом. Затем новый солдат занимает место на вершине стека.

Пример

Рассмотрим обработку солдат из примера.

Реализация алгоритма

Объявим стек s для хранения высот и индексов солдат.

stack<pair<int, int> > s; // (height, index)

Читаем входные данные.

scanf("%d", &n);

h.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &h[i]);

Последовательно обрабатываем n солдат.

for (i = 0; i < h.size(); i++)

{

Удаляем из стека солдат, чьи высоты не превышают высоту i-го солдата.

while (!s.empty() && s.top().first <= h[i])

s.pop();

Если стек пустой, то i-ый солдат имеет четкую видимость. То есть он видит всех солдат перед собой, и никто из них не блокирует ему вид.

if (s.empty())

printf("-1 ");

else

Текущий солдат в стеке является ближайшим предыдущим солдатом, рост которого превышает рост i - го солдата.

printf("%d ", s.top().second);

Заносим информацию о текущем солдате в стек.

s.push(make_pair(h[i], i));

}

Python реализация

Читаем входные данные.

n = int(input())

h = list(map(int, input().split()))

Объявим стек s для хранения высот и индексов солдат.

s = []

Последовательно обрабатываем n солдат.

for i in range(len(h)):

Удаляем из стека солдат, чьи высоты не превышают высоту i-го солдата.

while s and s[-1][0] <= h[i]:

s.pop()

Если стек пустой, то i-ый солдат имеет четкую видимость. То есть он видит всех солдат перед собой, и никто из них не блокирует ему вид.

if not s:

print("-1", end=" ")

Текущий солдат в стеке является ближайшим предыдущим солдатом, рост которого превышает рост i - го солдата.

else:

print(s[-1][1], end=" ")

Заносим информацию о текущем солдате в стек.

s.append((h[i], i))